package com.cuz.hot100;

import java.util.Arrays;

public class Q28ImplementStrStr {


    public static int indexOf(String source, String target) {
        if (source == null || target == null) {
            return -1;
        }
        if (source.length() == 0 && target.length() == 0) {
            return 0;
        }
        int sourceIndex = 0;
        int targetIndex = 0;
        char[] targetCharArray = target.toCharArray();
        char[] sourceCharArray = source.toCharArray();
        int sourceLen = sourceCharArray.length;
        int targetLen = targetCharArray.length;
        int[] kmpArray = kmpArray(targetCharArray);
        while (sourceIndex < sourceLen && targetIndex < targetLen) {
            if (sourceCharArray[sourceIndex] == targetCharArray[targetIndex]) {
                sourceIndex++;
                targetIndex++;
            } else if (kmpArray[targetIndex] == -1) {
                sourceIndex++;
            } else {
                targetIndex = kmpArray[targetIndex];
            }
        }
        if (targetIndex == targetLen) {
            return sourceIndex - targetLen;
        }
        return -1;
    }


    private static int[] kmpArray(char[] sourceCharArray) {
        if (sourceCharArray == null || sourceCharArray.length == 0) {
            return new int[0];
        }
        if (sourceCharArray.length == 1) {
            return new int[]{-1};
        }
        if (sourceCharArray.length == 2) {
            return new int[]{-1, 0};
        }
        int valueOfIndex2 = sourceCharArray[0] == sourceCharArray[1] ? 1 : 0;
        if (sourceCharArray.length == 3) {
            return new int[]{-1, 0, valueOfIndex2};
        }
        int len = sourceCharArray.length;
        int[] dp = new int[len];
        dp[0] = -1;
        dp[1] = 0;
        dp[2] = valueOfIndex2;
        for (int curIndex = 3; curIndex < len; curIndex++) {
            int preIndex = curIndex - 1;
            while (preIndex > 0) {
                if (sourceCharArray[curIndex - 1]
                        == sourceCharArray[dp[preIndex]]) {
                    dp[curIndex] = dp[preIndex] + 1;
                    break;
                } else {
                    preIndex = dp[preIndex];
                }
            }
        }
        return dp;
    }


    public static void main(String[] args) {

        String s = "aacdaabcdedld";
        int[] ints = kmpArray(s.toCharArray());
        System.out.println(Arrays.toString(ints));
    }

}
